﻿/*
 * ©2009-2010 XELF
 * http://xelf.info
 */

#if WINDOWS

using System;
using System.Numerics;

namespace XELF.Framework {

	/// <summary>
	/// 分数
	/// </summary>
	public partial struct BigFraction {
		/// <summary>
		/// 分子
		/// </summary>
		public BigInteger Numerator;
		/// <summary>
		/// 分母
		/// </summary>
		public BigInteger Denominator;
		public BigFraction(BigInteger numerator, BigInteger denominator) {
			Numerator = numerator;
			Denominator = denominator;
		}
		/// <summary>
		/// 約分する。
		/// </summary>
		public void Reduce() {
			var gcd = BigInteger.GreatestCommonDivisor(
			Numerator, Denominator);
			if (!gcd.IsZero) {
				Numerator /= gcd;
				Denominator /= gcd;
			}
		}
		public bool IsZero {
			get {
				return Numerator.IsZero && !Denominator.IsZero;
			}
		}
		public override string ToString() {
			return Numerator + "/" + Denominator;
		}

		public static BigFraction operator +(BigFraction a, BigFraction b) {
			var result = new BigFraction(b.Denominator * a.Numerator + a.Denominator * b.Numerator, a.Denominator * b.Denominator);
			//result.Reduce();
			return result;
		}
		public static void Add(ref BigFraction a, ref BigFraction b, out BigFraction result) {
			result = new BigFraction(b.Denominator * a.Numerator + a.Denominator * b.Numerator, a.Denominator * b.Denominator);
			//result.Reduce();
		}
		public static BigFraction operator -(BigFraction a, BigFraction b) {
			var result = new BigFraction(b.Denominator * a.Numerator - a.Denominator * b.Numerator, a.Denominator * b.Denominator);
			//result.Reduce();
			return result;
		}
		public static void Subtract(ref BigFraction a, ref BigFraction b, out BigFraction result) {
			result = new BigFraction(b.Denominator * a.Numerator - a.Denominator * b.Numerator, a.Denominator * b.Denominator);
			//result.Reduce();
		}
		public static BigFraction operator *(BigFraction a, BigFraction b) {
			var result = new BigFraction(a.Numerator * b.Numerator, a.Denominator * b.Denominator);
			//result.Reduce();
			return result;
		}
		public static void Multiply(ref BigFraction a, ref BigFraction b, out BigFraction result) {
			result = new BigFraction(a.Numerator * b.Numerator, a.Denominator * b.Denominator);
			//result.Reduce();
		}
		public static BigFraction operator /(BigFraction a, BigFraction b) {
			var result = new BigFraction(a.Numerator * b.Denominator, a.Denominator * b.Numerator);
			//result.Reduce();
			return result;
		}
		public static void Divide(ref BigFraction a, ref BigFraction b, out BigFraction result) {
			result = new BigFraction(a.Numerator * b.Denominator, a.Denominator * b.Numerator);
			//result.Reduce();
		}
		public static BigFraction Pow(BigFraction a, int b) {
			var result = new BigFraction(BigInteger.Pow(a.Numerator, b), BigInteger.Pow(a.Denominator, b));
			//result.Reduce();
			return result;
		}
		public void Invert() {
			var c = Denominator;
			Denominator = Numerator;
			Numerator = c;
		}

		/// <summary>
		/// 二項係数(Binomial Coefficient)
		/// </summary>
		/// <param name="n"></param>
		/// <param name="k"></param>
		/// <returns></returns>
		public static BigFraction Choose(uint n, uint k) {
			if (n == 0 && k > 0) return Zero;
			if (k == 0 || k == n) return One;
			if (k < 0 || k > n) throw new ArgumentOutOfRangeException("k");
			if (k * 2 > n) {
				k = n - k;
			}
			var n_k = n - k;
			BigFraction a = One;
			for (uint i = 1; i <= k; i++) {
				a *= new BigFraction(n_k + i, i);
			}
			return a;
		}

		public static readonly BigFraction Zero = new BigFraction(0, 1);
		public static readonly BigFraction One = new BigFraction(1, 1);
		public static readonly BigFraction Two = new BigFraction(2, 1);
		public static readonly BigFraction Three = new BigFraction(3, 1);
		public static readonly BigFraction Four = new BigFraction(4, 1);
		public static readonly BigFraction Five = new BigFraction(5, 1);
		public static readonly BigFraction Six = new BigFraction(6, 1);
		public static readonly BigFraction Seven = new BigFraction(7, 1);
		public static readonly BigFraction Eight = new BigFraction(8, 1);

		#region π

		/// <summary>
		/// ライプニッツの公式
		/// </summary>
		/// <param name="n"></param>
		/// <returns></returns>
		public static BigFraction Leibniz(int n) { // → π / 4
			BigFraction result = BigFraction.Zero;
			for (int i = 0; i <= n; i++) {
				var x = new BigFraction((i & 1) == 0 ? 1 : -1, i * 2 + 1);
				Add(ref result, ref x, out result);
			}
			return result;
		}

		/// <summary>
		/// π （BBPの公式）
		/// </summary>
		/// <param name="n"></param>
		/// <returns></returns>
		public static BigFraction Pi(int n) {
			BigFraction result = BigFraction.Zero;
			BigFraction sixteen = new BigFraction(16, 1);
			BigFraction a, b, c, d;
			var one = One;
			var two = Two;
			var four = Four;
			var five = Five;
			var six = Six;
			for (int i = 0; i <= n; i++) {
				var y = new BigFraction(8 * i, 1);
				Add(ref y, ref one, out a);
				a.Invert();
				Multiply(ref a, ref four, out a);
				Add(ref y, ref four, out b);
				b.Invert();
				Multiply(ref b, ref two, out b);
				Add(ref y, ref five, out c);
				c.Invert();
				Add(ref y, ref six, out d);
				d.Invert();
				Subtract(ref a, ref b, out a);
				Subtract(ref a, ref c, out a);
				Subtract(ref a, ref d, out a);
				var x = Pow(sixteen, i);
				Divide(ref a, ref x, out x);
				Add(ref result, ref x, out result);
			}
			return result;
		}

		#endregion
	}
}

#endif
